1. Field of the Invention
The present invention relates generally to a decoding circuit and a decoding method thereof. More particularly, the invention relates to a BCH code (Bose-Chaudhuri-Hocquenghem code) decoding circuit which is used in a system where a plurality of code words are transmitted in interleaving manner and simultaneous decoding of plurality of code words is required on reception side.
2. Description of the Related Art
Conventionally, as Read-Solomon decoder, a system assigning Read-Solomon decoder per code word has been known in the art. Such system has been disclosed in Hideki IMAI, “Code Theory”, the Institute of Electronic Information and Communication Engineers, March, 1990 (hereinafter referred to as reference), or so forth.
However, the foregoing system has large circuit scale and large power consumption, and is not suitable for application where a plurality of code words are transmitted in interleaved form and simultaneous decoding of a plurality of code words is required on reception side.
A system construction upon constructing a system for simultaneously decoding L in number of code words using the prior art is shown in FIG. 22. In FIG. 22, first to (M)th reception code words are input to first to (M)th decoders 11-1 to 11-M. The first to (M)th decoders 11-1 to 11-M perform decoding and output first to (M)th corrected code words.
Construction of each of the first to (M)th decoders 11-1 to 11-M is shown in FIG. 23. For the purpose of disclosure, the decoders (11-1 to 11-M) will be generally identified by 11. In FIG. 23, the decoder 11 is constructed with a syndrome calculating portion 12, an error position polynomial expression/error value polynomial expression leading portion 13, an error position/error value calculating portion 14, a reception code word storing portion 15 and an error correcting portion 16.
For example, considering the case of decoding of the code word having code length of 255 bytes which is consisted of an information signal of 239 bytes and a redundancy inspection signal of 16 bytes, a signal of 1 byte is converted into the element of Galois field containing 256 elements. A primitive polynomial of Galois field is x8+x4+x3+x2+1. Assuming primitive element is α, generating polynomial G(x) is expressed by:G(x)=(x−1) (x−α2) . . . (x−α15)  (1)Discussion for the foregoing example will be given hereinafter.
A construction of syndrome calculating portion 12 in FIG. 23 is shown in FIG. 24. The syndrome calculating portion 12 is constructed with sixteen Galois field adders 121-1 to 121-16, sixteen feedback shift registers 122-1 to 122-16, sixteen Galois field constant multiplier (×α0, ×α1, . . . , ×α15) 123-1 to 123-16, a counter 126, Galois filed constant multiplier input signal selectors 124-1 to 124-16 and syndrome coefficient output selectors 125-1 to 125-16.
The syndrome calculating portion 12 calculates a coefficient Si of syndrome polynomial S(z) defined by:S(z)=S0+S1z+S2z2+ . . . +S15z15  (2)The syndrome coefficient Si is defined by:                                                                                           S                  i                                =                                  Y                  ⁡                                      (                                          α                      1                                        )                                                                                                                          =                                                      Y                    0                                    +                                                            Y                      1                                        ⁢                                          α                      1                                                        +                                                            Y                      2                                        ⁢                                          α                                              2                        ⁢                        i                                                                              +                                                            Y                      3                                        ⁢                                          α                                              3                        ⁢                        i                                                                              +                  …                  ⁢                                                                           +                                                            Y                      254                                        ⁢                                          α                                              254                        ⁢                        i                                                                                                                                ⁢                                  ⁢                              i            =            0                    ,                      …            ⁢                                                   ⁢            15                                              (        3        )            Here, in the foregoing expression (3), Y(x) is a reception polynomial and α is primitive element.
The expression (2) can be modified with the expression (3) as follow:Si=( . . . ((Y254αi+Y253)αi+Y252)αi+ . . . +Y1)αi+Y0  (4)Accordingly, in order to sequentially calculate syndrome coefficient relative to the reception code word Yj, calculation is progressed as:Si←(Siαi+Yj)
The reception code word (Y254, . . . , Y0) is input per one byte in synchronism with a clock. When the counter 126 is input the leading end Y254 of the reception code word, the counter 126 is reset to zero. Subsequently, the counter 126 is incremented a counter value per clock. The counter 126 controls the Galois field constant multiplier input signal selectors 124-1 to 124-16 and the syndrome coefficient output selectors 125-1 to 125-16 by the counter value.
When the counter value is zero, the Galois field constant multiplier input signal selectors 124-1 to 124-16 output zero. In this case, the leading end Y254 of the reception code word is set to the feedback shift registers 122-1 to 122-16. When the counter value is other than zero, Galois field constant multiplier input signal selectors 124-1 to 124-16 output value of the outputs of the feedback shift registers 122-1 to 122-16.
When the counter value is j (0<j<255), the outputs of feedback shift registers 122-1 to 122-16 are multiplied by a constant (αi) by the Galois field constant multipliers 123-1 to 123-16 and are added the reception code word Y245−j in the Galois field adders 121-1 to 121-16, and the result of the adding is inputted to the feedback shift registers 122-1 to 122-16 and the content of the shift register is updated.
The reception code words (Y245, . . . , Y0) are input in sequential order from Y254 (descending order). When Y0 is read out, the contents of the shift registers 122-1 to 122-16 become Si. At this time, the counter value becomes 254.
When the counter value is 254, the syndrome coefficient output selectors 125-1 to 125-16 take the outputs of the feedback shift registers 122-1 to 122-16 as syndrome coefficients and output them to the error position polynomial and error value polynomial leading portion 13.
The error position polynomial and error value polynomial leading portion 13 leads error position polynomial and error value polynomial using Euclidean algorithm for outputting an error position polynomial coefficient and error value polynomial coefficient to the error position and error value calculating portion 14. The error position polynomial σ(z) is expressed by:σ(z)=σ0+σ1z+ . . . +σ8z8  (5)On the other hand, the error value polynomial ω(z) is expressed byω(z)=ω0+ω1z+ . . . +ω7z7  (6)Euclidean algorithm has been disclosed in the foregoing reference, associated disclosure of the above-identified reference is herein incorporated by reference for the sake of disclosure.
The error position and error value calculating portion 14 leads the error position and the error value from the error position polynomial coefficient and the error value polynomial coefficient to output to an error correcting portion 16. Here, error value denominator polynomial σodd(z) is introduced.
The error value denominator polynomial a σodd(z) is one taking out odd number order component from the error position polynomial σ(z) and is expressed by:σodd(z)=σ1z+σ3z3+σ5z5+σ7z7  (7)
By sequentially inputting powers of α(αi) (i=1 . . . , 255) to the error position position polynomial σ(Z), when σ(αi)=0 is established, it can be appreciated that error is caused in (255−i)th order component Y255−i of the reception word. Such method for deriving a solution by sequentially replacing powers of α(αi) is referred to as Chien solution. The theoretical background of capability of leading the error position from the error position polynomial has been disclosed in the above-identified reference. The relevant portion of the disclosure in the reference is herein incorporated by reference for the sake of disclosure.
On the other hand, the error value caused in the (255−i)th order component Y255−i is expressed by ω(αi)/σodd(αi). A numerator of error value (ω(αi)) and denominator (σodd(αi)) are derived by using Chien solution.
A construction of the error position and error value calculating portion 14 set forth above is illustrated in FIG. 25. In FIG. 25, the error position and error value calculating portion 14 is constructed with an error position Chien solution portion 141, an error value denominator Chien solution portion 142, an error value numerator Chien solution portion 143, an error position judgment portion 144, a Galois field division circuit 145 and a counter 146.
The counter 146 is responsive to input of the error position polynomial coefficient σ0, . . . σ8, and error value polynomial coefficient ω0, . . . , ω7, to be reset to zero. Subsequently, the counter 146 is incremented the counter value per clock.
The construction of the error position Chien solution portion 141 is shown in FIG. 26. In FIG. 26, the error position Chien solution portion 141 is constructed with nine feedback shift registers 1412-1 to 1412-9, nine Galois field constant multipliers 1413-1 to 1413-9, nine feedback register input signal selectors 1411-1 to 1411-9, and nine-input Galois field adder 1414.
Using FIG. 26, discussion will be given for operation of the error position Chien solution portion 141. When the counter value is zero, the feedback shift registers 1411-1 to 1411-9 outputs error position polynomial coefficients σ0, . . . , σ8 to set the error position polynomial coefficients σ0, . . . , σ8 to the feedback shift registers 1412-1 to 1412-9. The outputs of the feedback shift registers 1412-1 to 1412-9 storing the (k)th order error position polynomial coefficient σk are multiplied for αk times by the Galois field constant multipliers 1413-1 to 1413-9.
When the counter value is other than zero, the feedback shift register input signal selectors 1411-1 to 1411-9 select outputs of the Galois field constant multipliers 1413-1 to 1413-9. Accordingly, when the counter value is other than zero, the feedback shift registers 1412-1 to 1412-9 are updated by the outputs of the Galois field constant multipliers 1413-1 to 1413-9.
The outputs of the feedback shift registers 1412-1 to 1412-9 are input to nine-input Galois field adder 1414. The nine-input Galois field adder 1414 outputs a result of addition to the error position judgment circuit 144. Shifting is repeated for 255 times. Upon (i)th shift, the output of the nine-input Galois field adder 1414 becomes σ(αi).
The error value denominator Chien solution portion 142 is realized by a circuit construction similar to the error position Chien solution portion 141 to output σodd(αi) at (i)th shift. The error value numerator Chien solution portion 143 is realized by similar circuit construction as the error position Chien solution portion 141 to output ω(αi) at (i)th shift.
Upon (i)th shift, σodd(αi) output from the error value denominator Chien solution portion 142 and ω(αi) output from the error value numerator Chien solution portion 143 are input to a Galois filed division circuit 145. The Galois filed division circuit 145 outputs the result of division ω(αi)/σodd(αi) as error value to the error position judgment circuit 144.
Upon (i)th shift, σ(αi) output from the error position Chien solution portion 141 is input to the error position judgment circuit 144. The error position judgment circuit 144 makes judgment upon occurrence of error in the (255−i)th order component Y255−1 when σ(αi)=0, for outputting the error position 255−i and error value ω(αi)/σodd(αi) input from the Galois field division circuit 145 to the error correcting portion 16. The error position judgment circuit 144 makes judgment from the counter value of current shifting number.
The error correcting portion 16 corrects received code word stored in the received code word storing portion 15 on the basis of the error position and the error value input from the error position and error value calculating portion 14 to externally output the corrected code word.
In the conventional decoder, since circuit scale is large and power consumption is also large, a plurality of code words are transmitted in interleaved manner, and is not suitable for application in a system which is required to simultaneously decode a plurality of code word on reception side.